package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}15:54
 */
public class LeetCode122 {
    // 方法一：贪心算法 今天买 明天卖（只有赚钱的时候再卖）
    public int maxProfit(int[] prices) {
        int res = 0;
        int len = prices.length;
        for (int i = 0; i < len - 1; i++){
            int diff = prices[i + 1] - prices[i];
            if (diff > 0){
                res  += diff;
            }
        }
        return res;
    }
    // 方法二：动态规划
    public int maxProfit2(int[] prices) {
        if (prices == null || prices.length == 0){
            return 0;
        }

        int len = prices.length;
        // 0:持有现金
        // 1:持有股票
        // 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0
        int[][] dp = new int[len][2];

        // 第一天的状态
        dp[0][0] = 0;
        dp[0][1] = -prices[0]; // 成本
        for (int i = 1; i < len; i++) {
            // 这两行调换顺序也是可以的
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];

    }

    // 这里可以有无限次的买入和卖出，也就是说 买入 状态之前可拥有 卖出 状态，所以买入的转移方程需要变化。
    // 所以最终的状态方程为 buy = max(buy,sell - buy); sell = max(sell,prices[i] - buy)
    public int maxProfit3(int[] prices){
        if (prices.length <= 1){
            return 0;
        }
        int buy = -prices[0];
        int sell = 0;
        for (int i = 1; i < prices.length; i++){
            sell = Math.max(sell,prices[i] + buy);// sell永远是你捞了多少钱
            buy = Math.max(buy,sell - prices[i]);// buy始终是你现在手中的钱
        }
        return sell;
    }

    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(new LeetCode122().maxProfit2(prices));
    }
}
